#include<iostream>
#include<vector>
#include<stack>
#include<string>
#include<queue>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    private:
    vector<vector<int>> val;
    deque<int> index;

    public:
    int ans1(vector<vector<string>>& grid){
        int row = grid.size();
        int col = grid[0].size();
        if(row == 0){
            return 0;
        }
        int num_islands = 0;
        for(int i = 0; i != row; i++){
            for(int j = 0; j != col; j++){
                if(grid[i][j] == "1"){
                    num_islands++;
                    dfs(grid, i, j);
                }
            }
        }

        return num_islands;
    }

    //深度优先
    void dfs(vector<vector<string>>&grid, int r, int c){
        int row = grid.size();
        int col = grid[0].size();

        grid[r][c] = "0";
        if(r-1 >= 0 && grid[r-1][c] == "1"){
            dfs(grid, r-1, c);
        }
        if(r+1 < row && grid[r+1][c] == "1"){
            dfs(grid, r+1, c);
        }
        if(c-1 >= 0 && grid[r][c-1] == "1"){
            dfs(grid, r, c-1);
        }
        if(c+1 < col && grid[r][c+1] == "1"){
            dfs(grid, r, c+1);
        }
    }

    //广度优先
    int ans2(vector<vector<string>>& grid){
        int row = grid.size();
        int col = grid[0].size();
        if(row == 0){
            return 0;
        }

        int num_islands = 0;
        for(int i = 0; i != row; i++){
            for(int j = 0; j != col; j++){
                if(grid[i][j] == "1"){
                    num_islands++;
                    grid[i][j] = "0";
                    queue<pair<int, int>> neighbors;
                    neighbors.push({i, j});
                    while(!neighbors.empty()){
                        pair<int, int> rc = neighbors.front();
                        neighbors.pop();
                        int r = rc.first, c = rc.second;
                        if(r-1 >= 0 && grid[r-1][c] == "1"){
                            neighbors.push({r-1, c});
                            grid[r-1][c] = "0";
                        }
                        if(r+1 < row && grid[r+1][c] == "1"){
                            neighbors.push({r+1, c});
                            grid[r+1][c] = "0";
                        }
                        if(c-1 >= 0 && grid[r][c-1] == "1"){
                            neighbors.push({r, c-1});
                            grid[r][c-1] = "0";
                        }
                        if(c+1 < col && grid[r][c+1] == "1"){
                            neighbors.push({r, c+1});
                            grid[r][c+1] = "0";
                        }
                    }
                }
            }
        }

        return num_islands;
    }

};



void test1(){
    vector<vector<string>> grid = {
        {"1","1","1","1","0"},
        {"1","1","0","1","0"},
        {"1","1","0","0","0"},
        {"0","0","0","0","0"}
    };

    Solution s;
    int ret = s.ans1(grid);
    cout << ret << endl;
    
}

void test2(){
    vector<vector<string>> grid = {
        {"1","1","0","0","0"},
        {"1","1","0","0","0"},
        {"0","0","1","0","0"},
        {"0","0","0","1","1"}
    };

    Solution s;
    // int ret = s.ans1(grid);
    int ret = s.ans2(grid);
    cout << ret << endl;
    
}



int main(void){
    test1();
    cout << "-----------------------------" << endl;
    test2();

    return 0;
}